package com.future;

/**
 * Description: 63. 不同路径 II
 *
 * @author weiruibai.vendor
 * Date: 2022/6/11 09:56
 */
public class Solution_63 {

    public static void main(String[] args) {
        int[][] obstacleGrid = new int[][]{{0, 0, 0}, {0, 1, 0}, {0, 0, 0}};
        //obstacleGrid = new int[][]{{0, 1}, {0, 0}};
        System.out.println(uniquePathsWithObstacles(obstacleGrid));
        System.out.println(uniquePathsWithObstacles_dp(obstacleGrid));
    }

    /**
     * 暴力超时
     *
     * @param obstacleGrid
     * @return
     */
    public static int uniquePathsWithObstacles(int[][] obstacleGrid) {
        return process(obstacleGrid, 0, 0);
    }

    private static int process(int[][] obstacleGrid, int i, int j) {
        if (i >= obstacleGrid.length || j >= obstacleGrid[0].length || obstacleGrid[i][j] == 1) {
            return 0;
        }
        if (i == obstacleGrid.length - 1 && j == obstacleGrid[0].length - 1) {
            return 1;
        }
        // 右
        int count1 = process(obstacleGrid, i, j + 1);
        // 下
        int count2 = process(obstacleGrid, i + 1, j);
        return count1 + count2;
    }

    /**
     * good
     *
     * @param obstacleGrid
     * @return
     */
    public static int uniquePathsWithObstacles_dp(int[][] obstacleGrid) {
        int M = obstacleGrid.length;
        int N = obstacleGrid[0].length;
        int dp[][] = new int[M][N];
        for (int i = 0; i < M; i++) {
            for (int j = 0; j < N; j++) {
                dp[i][j] = -1;
            }
        }
        return process_dp(obstacleGrid, 0, 0, dp);
    }

    private static int process_dp(int[][] obstacleGrid, int i, int j, int dp[][]) {
        if (i >= obstacleGrid.length || j >= obstacleGrid[0].length || obstacleGrid[i][j] == 1) {
            return 0;
        }
        if (dp[i][j] != -1) {
            return dp[i][j];
        }
        int val;
        if (i == obstacleGrid.length - 1 && j == obstacleGrid[0].length - 1) {
            val = 1;
        } else {
            // 右
            int count1 = process_dp(obstacleGrid, i, j + 1, dp);
            // 下
            int count2 = process_dp(obstacleGrid, i + 1, j, dp);
            val = count1 + count2;
        }
        dp[i][j] = val;
        return dp[i][j];
    }

}
